class ArrayDeque:
    """基于环行数组实现的双向队列"""

    def __init__(self, capacity: int = 10):
        self._nums: list[int] = [0] * capacity
        self._front: int = 0
        self._size: int = 0

    def capacity(self) -> int:
        """返回队列的容量"""
        return len(self._nums)

    def size(self) -> int:
        """获取双向队列的长度"""
        return self._size

    def is_empty(self) -> bool:
        """判断双向队列是否为空"""
        return self._size == 0

    def index(self, i: int) -> int:
        """计算环形数组索引"""
        # 当 i 超过数组尾部后, 回到头部
        # 当 i 超过数组头部后, 回到尾部
        return (self._front + i) % self.capacity()

    def push_first(self, num: int) -> None:
        """在队列头部添加元素"""
        if self._size == self.capacity():
            raise Exception("队列已满")
        # 队首指正针回退一位
        # 通过取余操作实现 front 越过数组头部后回到尾部
        self._front = self.index(self._front - 1)
        # 将 num 添加到队首
        self._nums[self._front] = num
        self._size += 1

    def push_last(self, num: int) -> None:
        """在队列尾部添加元素"""
        if self._size == self.capacity():
            raise Exception("队列已满")
        # 队尾指针后移一位
        # 通过取余操作实现 rear 越过数组尾部后回到头部
        rear = self.index(self._front + self._size)
        self._nums[rear] = num
        self._size += 1

